package com.leetcodehot.problems;

import jdk.internal.net.http.common.Pair;

import java.util.Map;

public class problems1123 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 做法一：暴力版本，先dfs一轮看一下，最深的是哪些
     */
    /*
    private int maxdepth = 0;
    private List<TreeNode> treeNodelist = new ArrayList<>();

    private void maxDepth(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (maxdepth < depth) {
            maxdepth = depth;
            treeNodelist.clear();
            treeNodelist.add(root);
        } else if (maxdepth == depth) {
            treeNodelist.add(root);
        }
        maxDepth(root.left, depth + 1);
        maxDepth(root.right, depth + 1);
    }

    private TreeNode dfs(TreeNode root, List<TreeNode> treeNodelist) {
        if (root == null) {
            return null;
        }
        for (TreeNode treeNode : treeNodelist) {
            if (treeNode.val == root.val) {
                return root;
            }
        }
        TreeNode left = dfs(root.left, treeNodelist);
        TreeNode right = dfs(root.right, treeNodelist);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        maxDepth(root, 0);
        return dfs(root, treeNodelist);
    }
    */


    /**
     * 做法二，改进版本，只用一次递归
     * 原本来的做法改进为；maxDepth每次维护最大即可，
     * 递的过程把深度递进去
     * 归的过程归最大深度
     */
    private int maxDepth = -1;
    private TreeNode ans;

    private int dfs(TreeNode node, int depth) {
        if (node == null) {
            maxDepth = Math.max(maxDepth, depth);
            return depth;
        }
        int leftMaxDepth = dfs(node.left, depth + 1);
        int rightMaxDepth = dfs(node.right, depth + 1);
        if (leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth) {
            ans = node;
        }
        return Math.max(leftMaxDepth, rightMaxDepth);
    }

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

}
